#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
    vector<vector<string>> ans;
    vector<string> path;
    // bool horizontal[12];
    bool vertical[12];
    bool left[20];
    bool right[20];
    int n;
public:
    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        dfs(0);
        return ans;
    }

    void dfs(int i){
        if(i == n){
            ans.emplace_back(path);
            return;
        }
        string cur = string(n, '.');
        for(int j = 0; j < n; ++j){
            if(vertical[j] && left[i - j + n] && right[i + j]){
                cur[j] = 'Q';
                path.emplace_back(cur);
                vertical[j] = true;
                left[i - j + n] = true;
                right[i + j] = true;
                
                dfs(i + 1);
                
                cur[j] = '.';
                path.pop_back();
                vertical[j] = false;
                left[i - j + n] = false;
                right[i + j] = false;
            }
        }
    }
};

class Solution1 {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + ((r - l) >> 1);
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};


int main(){
    Solution1 sol;
    vector<int> nums = {1,3,5,6};
    sol.searchInsert(nums, 5);
}